/*
 * @(#)MathUtil.java	1.0 Apr 26, 2008
 *
 *	The MIT License
 *
 *	Copyright (c) 2008 Malachi de AElfweald <malachid@gmail.com>
 *
 *	Permission is hereby granted, free of charge, to any person obtaining a copy
 *	of this software and associated documentation files (the "Software"), to deal
 *	in the Software without restriction, including without limitation the rights
 *	to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 *	copies of the Software, and to permit persons to whom the Software is
 *	furnished to do so, subject to the following conditions:
 *
 *	The above copyright notice and this permission notice shall be included in
 *	all copies or substantial portions of the Software.
 *
 *	THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 *	IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 *	FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 *	AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 *	LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 *	OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 *	THE SOFTWARE.
 */
package org.eoti.math;

import org.eoti.math.prime.PrimeFactor;

import java.math.BigInteger;
import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.*;

public class MathUtil
{
	protected static BigInteger BigIntegerZERO = BigInteger.ZERO;
	protected static BigInteger BigIntegerONE = BigInteger.ONE;
	protected static BigInteger BigIntegerTWO = BigInteger.valueOf(2);
	protected static BigInteger BigIntegerTHREE=BigInteger.valueOf(3);
	protected static BigInteger FactorialBreakpoint = BigInteger.valueOf(96);
	protected static BigDecimal BigDecimalZERO = BigDecimal.ZERO;
	protected static BigDecimal BigDecimalONE = BigDecimal.ONE;
	protected static BigDecimal BigDecimalTWO = new BigDecimal(2);
	protected static BigDecimal BigDecimalFOUR = new BigDecimal(4);

	public static boolean isDivisible(BigInteger isThisNumberDivisible, BigInteger byThisNumber)
	{
		return isThisNumberDivisible.mod(byThisNumber).equals(BigIntegerZERO);
	}

	public static BigInteger lowest(int numBits)
	{
		return BigIntegerTWO.pow(numBits-1);// -1 cuz 2^0=1
	}

	public static BigInteger highest(int numBits)
	{
		return BigIntegerTWO.pow(numBits).subtract(BigIntegerONE);
	}

	public static BigInteger sqrt(BigInteger number)
	{
		return sqrt(number, BigIntegerONE);
	}

	public static BigDecimal sqrt(BigDecimal number, RoundingMode rounding)
	{
		return sqrt(number, BigDecimalONE, rounding);
	}

	public static BigDecimal sqrt(BigDecimal number, BigDecimal guess, RoundingMode rounding)
	{
		BigDecimal result = BigDecimalZERO;
		BigDecimal flipA = result;
		BigDecimal flipB = result;
		boolean first = true;
		while( result.compareTo(guess) != 0 )
		{
			if(!first)
				guess = result;
			else
				first=false;

			result = number.divide(guess, rounding).add(guess).divide(BigDecimalTWO, rounding);
			// handle flip flops
			if(result.equals(flipB))
				return flipA;

			flipB = flipA;
			flipA = result;
		}
		return result;
	}

	public static BigDecimal[] quadratic(BigDecimal a, BigDecimal b, BigDecimal c, RoundingMode rounding)
	{
		// ax^2 + bx + c = 0
		BigDecimal part1 = b.negate();
		BigDecimal part2 = sqrt(b.multiply(b).subtract(BigDecimalFOUR.multiply(a).multiply(c)), rounding);
		BigDecimal part3 = BigDecimalTWO.multiply(a);
		BigDecimal[] toRet = new BigDecimal[2];
		toRet[0] = (part1.subtract(part2)).divide(part3, RoundingMode.CEILING);
		toRet[1] = (part1.add(part2)).divide(part3, RoundingMode.CEILING);
		return toRet;
	}


	protected static BigInteger sqrt(BigInteger number, BigInteger guess)
	{
		// ((n/g) + g)/2: until same result twice in a row
//		BigInteger result = number.divide(guess).add(guess).divide(BigIntegerTWO);
//		if(result.compareTo(guess) == 0)
//			return result;
//
//		return sqrt(number, result);

		// redoing this to avoid StackOverFlow
		BigInteger result = BigIntegerZERO;
		BigInteger flipA = result;
		BigInteger flipB = result;
		boolean first = true;
		while( result.compareTo(guess) != 0 )
		{
			if(!first)
				guess = result;
			else
				first=false;

			result = number.divide(guess).add(guess).divide(BigIntegerTWO);
			// handle flip flops
			if(result.equals(flipB))
				return flipA;

			flipB = flipA;
			flipA = result;
		}
		return result;

	}

	public static boolean isEven(BigInteger number)
	{
//		System.out.println("isEven("+number+")=("+number.getLowestSetBit()+"==0)=="+(number.getLowestSetBit() == 0));
		return number.getLowestSetBit() != 0;
	}

	public static boolean isOdd(BigInteger number)
	{
		return !isEven(number);
	}

	protected static BigInteger naiveFactorial(BigInteger toFactor)
	{
		if(toFactor.equals(BigIntegerZERO)) return BigIntegerONE;
		if(toFactor.equals(BigIntegerONE)) return toFactor;

		BigInteger toRet = toFactor;
		while(!toFactor.equals(BigIntegerONE))
		{
			toFactor = toFactor.subtract(BigIntegerONE);
			toRet = toRet.multiply(toFactor);
		}

		return toRet;
	}

	protected static BigInteger pairedFactor(BigInteger toFactor)
	{
//		if(toFactor.mod(BigIntegerTWO).equals(BigIntegerZERO))
		if(isEven(toFactor))
			return pairedEvenFactor(toFactor);

		return pairedOddFactor(toFactor);
	}

	protected static BigInteger pairedEvenFactor(BigInteger toFactor)
	{
		BigInteger half = toFactor.divide(BigIntegerTWO).add(BigIntegerONE);
		//BigInteger pairs = toFactor.subtract(half);
		BigInteger current = half.add(BigIntegerONE).multiply(half.subtract(BigIntegerONE));
		BigInteger total = current.multiply(half);
		BigInteger diff = BigIntegerTHREE;
		BigInteger last = toFactor.multiply(BigIntegerTWO);
		while(!current.equals(last))
		{
			current = current.subtract(diff);
			diff = diff.add(BigIntegerTWO);
			total = total.multiply(current);
		}

		return total;
	}

	protected static BigInteger pairedOddFactor(BigInteger toFactor)
	{
		BigInteger half = toFactor.add(BigIntegerONE).divide(BigIntegerTWO);
		//BigInteger pairs = half.subtract(BigIntegerZERO);
		BigInteger current = half.multiply(half.add(BigIntegerONE));
		BigInteger total = current;
		BigInteger diff = BigIntegerTWO;
		BigInteger last = toFactor.multiply(BigIntegerTWO);
		while(!current.equals(last))
		{
			current = current.subtract(diff);
			diff = diff.add(BigIntegerTWO);
			total = total.multiply(current);
		}

		return total;
	}

	public static BigInteger factorial(BigInteger toFactor)
	{
		if(toFactor.compareTo(FactorialBreakpoint) < 0)
			return naiveFactorial(toFactor);

		// naiveFactor seems to be faster for everything lower than 96
		// 96 seems to bounce back and forth with which is faster
		return pairedFactor(toFactor);
	}

	public static Collection<PrimeFactor> factor(BigInteger toFactor)
	{
		HashMap<BigInteger, PrimeFactor> factors = new HashMap<BigInteger, PrimeFactor>();
		boolean isPrime = true;
		BigInteger lowest = null;
		BigInteger p1, p2, AB;

		BigInteger dividend = toFactor;
		BigInteger divisor = BigInteger.ONE;
		BigInteger col = BigIntegerTWO;
		BigInteger center = toFactor.divide(BigIntegerTWO);
		while(col.compareTo(center) <= 0)
		{
			dividend = dividend.multiply(toFactor.subtract(col.subtract(BigInteger.ONE)));
			divisor = divisor.multiply(col);

			p1 = dividend.divide(divisor).mod(toFactor);
			if(!p1.equals(BigInteger.ZERO))
				isPrime = false;

			if(! (p1.equals(BigInteger.ZERO) || p1.equals(BigInteger.ONE) || p1.equals(toFactor)) ) // ignore these
			{
				p2 = toFactor.divide(p1);
				AB = p1.multiply(p2);

				if(AB.equals(toFactor))
				{
					if(p1.subtract(p2).signum() < 0)//p1 < p2
					{
						if((lowest == null)||(p1.subtract(lowest).signum() < 0))
							lowest = p1;
					}else{
						if((lowest == null)||(p2.subtract(lowest).signum() < 0))
							lowest = p2;
					}
				}
			}

			col = col.add(BigInteger.ONE);
		}

		if(isPrime)
		{
			factors.put(toFactor, new PrimeFactor(toFactor, BigInteger.ONE));
		}else{
			p1 = lowest;
			for(PrimeFactor p1Factor : factor(p1))
			{
				PrimeFactor factor = factors.get(p1Factor.getPrime());
				if(factor == null)
					factors.put(p1Factor.getPrime(), p1Factor);
				else
					factors.put(factor.getPrime(), new PrimeFactor(factor.getPrime(), factor.getPower().add(p1Factor.getPower())));
			}

			p2 = toFactor.divide(p1);
			for(PrimeFactor p2Factor : factor(p2))
			{
				PrimeFactor factor = factors.get(p2Factor.getPrime());
				if(factor == null)
					factors.put(p2Factor.getPrime(), p2Factor);
				else
					factors.put(factor.getPrime(), new PrimeFactor(factor.getPrime(), factor.getPower().add(p2Factor.getPower())));
			}
		}

		return factors.values();
	}

}
